High speed computation is a critical design factor in many systems, such as computers, signal processors, and process controllers. These systems increasingly rely on LSI integrated circuits to perform the multiplication functions. The most critical design parameter for the multiplication circuits is the speed at which the multiplication is performed; but also of great importance is the silicon area required for the circuit implementation and the ease of the layout of the circuit design.
Previously developed high speed multipliers employ a Booth-Wallace tree parallel array approach. The Booth technique recodes one operand as a signed digit radix four number. The partial products of the multiplication are formed by multiplying the radix four digit times the second operand. The resultant partial products from the multiplication are reduced approximately in half from a binary parallel array, because the radix four representation contains half as many digits as the binary representation.
The partial products can be further reduced by Octal recoding, wherein a signed digit radix eight number (each digit comprises three bits) is used. The Octal recoding reduces the number of partial products by two-thirds; however, the technique is heretofore not practical because it requires partial products that are multiples of three. Since multiples of three cannot be generated simply by a shift, but require a shift and an add operation, the advantage of the reduced partial products is negated by the additional time for the add operation.
A Wallace tree approach is used in high speed multipliers because it permits adding partial products in parallel rather than as a linear sequence in the pure parallel array approach. The major disadvantage of the Wallace tree is the complex routing which is required to calculate separate sum and carry streams. The design and layout of the Wallace tree circuit is even more complex due to the fact that the number of digits in each column of the partial product array changes with the place value of the digit. Thus, Wallace tree approaches tend to be routing intensive and have little iterative structure.
Recently, a binary tree approach has been developed wherein a signed digit redundant logic representation of numbers is employed along with a radix two operand. This approach is described in N. Takagi, H. Yasuura, and S. Yajima, High-Speed VLSI Multiplication Algorithm with a Redundant Binary Addition tree, IEEE Transactions On Computers, Vol. C-34, No. 9, Sept., 1985, pp. 789-795. The proposed multiplier described in the article uses a signed digit representation in which each digit may be a "0", "1", or "-1". The signed digit representation allows parallel addition of two N-digit numbers performed in a constant time independent of the number of digits in the number without carry propagation. Because the signed digit representation uses two bits for each digit, the addition is more complex, therefore slower. However, the layout of the circuit is simpler than the Wallace tree layout, and the slowness in speed is somewhat offset by the avoidance of the carry chain.
Thus, a need has arisen in the industry for a high speed multiplier having a less complex layout to reduce chip area size, while not sacrificing the speed of the multiplication.